package mo.offer_version2;

public class L04 {

    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int m = matrix.length;
        if (m == 0) {
            return target == 0;
        }
        int n = matrix[0].length;
        if (n == 0) {
            return false;
        }
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] > target) {
                return false;
            } else {
                int nl = 0;
                int nr = n - 1;
                while (nl <= nr) {
                    int nmid = nl + (nr -nl) / 2;
                    if (matrix[i][nmid] == target) {
                        return true;
                    } else if (matrix[i][nmid] < target) {
                        nl = nmid + 1;
                    } else {
                        nr = nmid - 1;
                    }
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        L04 test = new L04();
        System.out.println(test.findNumberIn2DArray(new int[][]{
                {1,   4,  7, 11, 15},
                {2,   5,  8, 12, 19},
                {3,   6,  9, 16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}
        }, 5));
    }

}
